package com.sise.Backtracking;

import com.sise.Tree.TreeNode;

import java.util.LinkedList;
import java.util.List;

/**
 *      剑指 Offer 34. 二叉树中和为某一值的路径
 *
 *      输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
 *      给定如下二叉树，以及目标和 target = 22，
 *
 *               5
 *              / \
 *             4   8
 *            /   / \
 *           11  13  4
 *          /  \    / \
 *         7    2  5   1
 *
 *      返回:
 *
 *      [
 *         [5,4,11,2],
 *         [5,8,4,5]
 *      ]
 *
 */
public class _offer_34_pathSum {

    List<List<Integer>> res = new LinkedList<>();           // 如果只是 List<List<Integer>> res 没有初始化，那么返回的结果为 null
    LinkedList<Integer> list = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        dfs(root, target);
        return res;
    }

    private void dfs(TreeNode root, int target){
        if (root == null) return;
        list.add(root.val);
        target -= root.val;
        if (target == 0 && root.left == null && root.right == null){
            res.add(new LinkedList<>(list));                // 这里需要进行 new 实例化，而不是当初的添加引用队列
        }

        dfs(root.left, target);                             // 做选择
        dfs(root.right, target);

        list.removeLast();                                  // 撤销选择

    }
}
